﻿// 601 逆序对2.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>


/*
http://oj.daimayuan.top/course/22/problem/653


有 n个数 a1,a2,…,an
，对于其中的两个数字 x,y，如果满足 x出现的位置在 y出现的位置前面并且 x比 y大，
 则称 (x,y)为数组 a的一个逆序对。请问数组 a的逆序对一共有多少个？形式化的说，请求出有多少组 (i,j)满足 i<j并且 ai>aj。

输入格式
第一行一个整数 n。

接下来一行 n个整数，a1,a2,…,an。

输出格式
一行一个数，表示答案。

样例输入
4
4 2 3 1
样例输出
5
样例解释
5 个逆序对分别为 (4,2),(4,3),(4,1),(2,1),(3,1)。

数据范围
对于 100%的数据，保证 2≤n≤100000,1≤ai≤n并且每个数字都只会出现一次。
*/

// 788. 逆序对的数量.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>

using namespace std;

const int N = 100010;
int a[N];
int n; long long  ans;
int tmp[N];


void mergesort(int arr[], int l, int r) {
	if (l >= r) return;
	int mid = l + r >> 1;
	mergesort(arr, l, mid); mergesort(arr, mid + 1, r);

	int i = l; int j = mid + 1; int k = 0;
	while (i <= mid && j <= r) {
		if (a[i] <= a[j]) {
			tmp[k++] = a[i++];
		}
		else {
			ans += mid - i + 1; //当前i 到mid  都比a[j]大  且j在mid+1~ r的范围 构成逆序对
			tmp[k++] = a[j++];
		}
	}
	while (i <= mid) tmp[k++] = a[i++];
	while (j <= r) tmp[k++] = a[j++];

	for (i = l, j = 0; j < k;) a[i++] = tmp[j++];
}



int main()
{
	cin >> n;
	for (int i = 0; i < n; i++) cin >> a[i];

	mergesort(a, 0, n - 1);

	cout << ans << endl;

	return 0;
}

